# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/12 16:29 
"""
"""
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

进阶：

一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-matrix-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

"""
# class Solution:
#     def setZeroes(self, matrix) :
#         """
#         Do not return anything, modify matrix in-place instead.
#         首先便利数组一次，如果某一个元素为0，那么将这个元素所在的行和列所对应的数组位置标记为true,
#         最后再次遍历该数组，用标记数组更新原数组即可
#         """
#         m,n=len(matrix),len(matrix[0])
#
#         #生成标志
#         rows,cols=[False]*m,[False]*n
#
#         for i in range(m):
#             for j in range(n):
#                 if matrix[i][j]==0:
#                     rows[i]=cols[j]=True
#
#         for i in range(m):
#             for j in range(n):
#                 if rows[i] or cols[j]:
#                     matrix[i][j]=0
#         return matrix

class Solution:
    def setZeroes(self, matrix) :
        """
        Do not return anything, modify matrix in-place instead.
        """
        m,n=len(matrix),len(matrix[0])

        #生成标志
        rows,cols=[False]*m,[False]*n

        for i in range(m):
            for j in range(n):
                if matrix[i][j]==0:
                    rows[i]=cols[j]=True

        for i in range(m):
            for j in range(n):
                if rows[i] or cols[j]:
                    matrix[i][j]=0
        return matrix


if __name__=="__main__":
    matrix1 = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
    matrix2 = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
    s=Solution()
    print(s.setZeroes(matrix1))
    print(s.setZeroes(matrix2))


